{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Problems"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 1-1 Comparison of running times\n",
    "\n",
    "> For each function $f(n)$ and time $t$ in the following table, determine the largest size $n$ of a problem that can be solved in time $t$ , assuming that the algorithm to solve the problem takes $f(n)$ microseconds."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "|            |  1 second  |  1 minute  |   1 hour   |   1 day    |  1 month   |   1 year   | 1 century  |\n",
    "|:----------:|:----------:|:----------:|:----------:|:----------:|:----------:|:----------:|:----------:|\n",
    "|  $lgn$   |$2^{10^6}$|$2^{6 \\times 10^{6}}$|$2^{3.6 \\times 10^{9}}$|$2^{8.64 \\times 10^{10}}$|$2^{2.59 \\times 10^{12}}$|$2^{3.15 \\times 10^{13}}$|$2^{3.15 \\times 10^{15}}$|\n",
    "|$\\sqrt{n}$|$10^{12}$ |$3.6 \\times 10 ^{15}$|$1.3 \\times 10^{19}$|$7.46 \\times 10^{21}$|$6.72 \\times 10^{24}$|$9.95 \\times 10^{26}$|$9.95 \\times 10^{30}$|\n",
    "|   $n$    |$10^6$|$6 \\times 10 ^{7}$|$3.6 \\times 10 ^{9}$|$8.64 \\times 10 ^{10}$|$2.59 \\times 10 ^{12}$|$3.15 \\times 10 ^{13}$|$3.15 \\times 10 ^{15}$|\n",
    "|  $nlgn$  |$6.24 \\times 10 ^{4}$|$2.8 \\times 10 ^{6}$|$1.33 \\times 10 ^{8}$|$2.76 \\times 10 ^{9}$|$7.19 \\times 10 ^{10}$|$7.98 \\times 10 ^{11}$|$6.86 \\times 10 ^{13}$|\n",
    "|  $n^2$   |$1000$|$7745$|$60000$|$293938$|$1609968$|$5615692$|$56156922$|\n",
    "|  $n^3$   |$100$|$391$|$1532$|$4420$|$13736$|$31593$|$146645$|\n",
    "|  $2^n$   |$19$|$25$|$31$|$36$|$41$|$44$|$51$|\n",
    "|   $n!$   |$9$|$11$|$12$|$13$|$15$|$16$|$17$|"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "import math\n",
    "\n",
    "def log2(n):\n",
    "    return math.log(n) / math.log(2)\n",
    "\n",
    "complexities = [lambda n: math.sqrt(n),\n",
    "                lambda n: n,\n",
    "                lambda n: n * log2(n),\n",
    "                lambda n: n ** 2,\n",
    "                lambda n: n ** 3,\n",
    "                lambda n: 2 ** n,\n",
    "                lambda n: math.factorial(n)]\n",
    "\n",
    "max_bound = [1e40, 1e20, 1e20, 1e10, 1e10, 100, 100]\n",
    "\n",
    "times = [1000 * 1000,\n",
    "         1000 * 1000 * 60,\n",
    "         1000 * 1000 * 60 * 60,\n",
    "         1000 * 1000 * 60 * 60 * 24,\n",
    "         1000 * 1000 * 60 * 60 * 24 * 30,\n",
    "         1000 * 1000 * 60 * 60 * 24 * 365,\n",
    "         1000 * 1000 * 60 * 60 * 24 * 365 * 100]\n",
    "\n",
    "print(' '.join(map(lambda v: '2^(' + '{:.2e}'.format(v) + ')', times)))\n",
    "\n",
    "for k in range(len(complexities)):\n",
    "    c = complexities[k]\n",
    "    vals = []\n",
    "    for t in times:\n",
    "        l, r = 0, int(max_bound[k])\n",
    "        max_n = 0\n",
    "        while l <= r:\n",
    "            mid = (l + r) // 2\n",
    "            val = c(mid)\n",
    "            if val == float('inf') or val > t:\n",
    "                r = mid - 1\n",
    "            else:\n",
    "                l = mid + 1\n",
    "                max_n = max(max_n, mid)\n",
    "        vals.append(max_n)\n",
    "    if k < 3:\n",
    "        print(' | '.join(map(lambda v: '{:.2e}'.format(v), vals)))\n",
    "    else:\n",
    "        print(' | '.join(map(lambda v: str(int(math.floor(v))), vals)))\n"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.6.3"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}
